#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len + 1, 1);
        vector<int> cnt(len + 1, 1);
        dp[0] = 1;
        int ans = 0;
        int res = 0;
        for (int i = 1; i < len; i++) {
            //dp[i]=dp[i-1];

            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    }
                    else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }

            }

        }

        for (int i = 0; i < len; i++) {
            ans = max(ans, dp[i]);
        }
        for (int i = 0; i < len; i++) {
            if (dp[i] == ans) {
                res += cnt[i];
            }
        }

        return res;
    }
};